package com.ly.algorithm.DataStructures.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Classname PolandNotation
 * @Description TODO
 * @Date 2020/4/22 20:31
 * @Author 冷心影翼
 */
public class PolandNotation {

    private Stack<Integer> numberStack = new Stack<>();

    public int cal(int num1,int num2,String op) {
        if ("+".equals(op)) {
            return num1+num2;
        }else if("-".equals(op)) {
            return num2-num1;
        }else if("*".equals(op)) {
            return num1 * num2;
        }else {
            return num2/num1;
        }
    }

    public int quantity(String c) {
        if(c.equals("*") || c.equals("/")) {
            return 2;
        }else if(c.equals("+") || c.equals("-")) {
            return 1;
        }else {
            return 0;
        }
    }

    private int parseSuffixExpression(String expression) {
        String[] strArr = expression.split(" ");
        for (String s : strArr) {
            if(s.matches("\\d+")) {
                numberStack.push(Integer.parseInt(s));
            }else {
                int num1 = numberStack.pop();
                int num2 = numberStack.pop();
                int res = cal(num1,num2,s);
                numberStack.push(res);
            }
        }
        return numberStack.peek();
    }

    public int parseExpression(String expression) {
        Stack<String> s1 = new Stack<>();

        List<String> s2 = new ArrayList<>();

        String[] s3 = expression.split(" ");
        for (String it: s3) {
            //数字直接压入 s2
            if(it.matches("\\d+")) {
                s2.add(it);
            }else if(it.equals("(")) {
                //（直接压入s1
                s1.push(it);
            }else if(it.equals(")")) {
                //） ， 弹出 s1 的运算符 到 s2 ，直到 遇到 ( 为止
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();
            }else {
                //当item的优先级 < s1栈运算符，将s1栈弹出并加入s2,在与 s1 栈顶比较
                while (s1.size()> 0 && quantity(it) <= quantity(s1.peek())) {
                    s2.add(s1.pop());
                }
                s1.push(it);
            }
        }

        while (s1.size()!=0) {
            s2.add(s1.pop());
        }
        String ex = "";
        for (String s : s2) {
            ex+= s+" ";
        }
        ex = ex.substring(0,ex.lastIndexOf(" "));
        return parseSuffixExpression(ex);
    }
}

class Test4{

    public static void main(String[] args) {
//        String expression = "3 4 + 5 * 6 -";
        String expression = "1.txt + ( ( 2 + 3 ) * 4 ) - 5";
        PolandNotation polandNotation = new PolandNotation();
        System.out.println(polandNotation.parseExpression(expression));
    }
}
